package vn.edu.hut.soict.automaton;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MinimalDFABuilder<T> {
	private DFA<T> dfa;
	/*
	 * The first confluence state.
	 */
	private State<T> firstState;

	/*
	 * The last state on the common prefix path.
	 */
	private State<T> lastState;

	/*
	 * States on the common prefix path.
	 */
	private List<State<T>> commonPrefix;

	/*
	 * The beginning index of the suffix substring.
	 */
	private int suffixIndex;

	/*
	 * The index of the first confluence state when calling method void commonPrefix(T[] string).
	 */
	private int currentIndex;

	private Map<State<T>, Integer> register;

	public MinimalDFABuilder(DFA<T> dfa) {
		this.dfa = dfa;
		register = new HashMap<State<T>, Integer>();
		for (State<T> state : dfa.getStates()) {
			register.put(state, state.getId());
		}
	}

	private void commonPrefix(T[] string) {
		commonPrefix = new ArrayList<State<T>>();
		State<T> state = dfa.getStartState();
		int i;
		for (i = 0; i < string.length && state != null; i++) {
			commonPrefix.add(state);
			Transition<T> curr = dfa.findFirstTransition(state, string[i]);
			if (curr == null) {
				state = null;
			}
			else {
				state = curr.getTarget();
			}
		}
		if (state != null) {
			commonPrefix.add(state);
			suffixIndex = i;
		}
		else {
			suffixIndex = i - 1;
		}
	}

	private State<T> firstConfluenceState() {
		for (int i = 0; i < commonPrefix.size(); i++) {
			if (commonPrefix.get(i).isConfluence()) {
				currentIndex = i;
				return commonPrefix.get(i);
			}
		}
		return null;
	}

	private State<T> clone(State<T> state) {
		State<T> newState = dfa.addNewState();
		List<Transition<T>> nextTransitions = state.getNextTransitions();
		for (int i = 0; i < nextTransitions.size(); i++) {
			dfa.addTransition(new Transition<T>(newState, nextTransitions.get(i).getTarget(), nextTransitions.get(i).getSymbol()));
		}
		return newState;
	}

	private void addSuffix(T[] sentence) {
		List<State<T>> processingStates = new ArrayList<State<T>>();
		State<T> currentState = lastState;
		for (int i = suffixIndex; i < sentence.length; i++) {
			processingStates.add(currentState);
			State<T> newState = dfa.addNewState();
			dfa.addTransition(new Transition<T>(currentState, newState, sentence[i]));
			currentState = newState;
		}
		currentState.setFinal(true);

		int index = sentence.length - 1;
		for (int i = processingStates.size() - 1; i >= 0; i--) {
			replaceOrRegister(processingStates.get(i), sentence[index--]);
		}
	}

	private void replaceOrRegister(State<T> state, T symbol) {
		Transition<T> transition = dfa.findFirstTransition(state, symbol);
		State<T> child = transition.getTarget();
		int newChildId = getEquivalentStateId(child);
		if (newChildId >= 0) {
			dfa.deleteState(child);
			dfa.addTransition(new Transition<T>(state, dfa.getStateByID(newChildId), symbol));
		}
		else {
			register.put(child, child.getId());
		}
	}

	private int getEquivalentStateId(State<T> state) {
		for (State<T> s : register.keySet()) {
			if (state.isEquivalent(s)) {
				return register.get(s);
			}
		}
		return -1;
	}

	public void unorederedAdd(T[] sentence) {
		// Find the common prefix and the suffix.
		commonPrefix(sentence);
		if (suffixIndex == sentence.length && commonPrefix.get(commonPrefix.size() - 1).isFinal()) {
			return;
		}

		// Find the first confluence state and append the suffix.
		firstState = firstConfluenceState();
		if (firstState == null) {
			lastState = commonPrefix.get(commonPrefix.size() - 1);
		}
		else {
			lastState = clone(commonPrefix.get(commonPrefix.size() - 1));
		}
		addSuffix(sentence);

		// If a confluence state is found, all states from the first confluence
		// state to the end of the common prefix path are cloned.
		State<T> currentState = null;
		if (firstState != null) {
			firstState = firstConfluenceState();
			for (int i = commonPrefix.size() - 2; i >= currentIndex; i--) {
				currentState = clone(commonPrefix.get(i));
				Transition<T> transition = dfa.findFirstTransition(currentState, sentence[i]);
				transition.setTarget(lastState);
				replaceOrRegister(currentState, sentence[i]);
				lastState = currentState;
			}
			Transition<T> transition = dfa.findFirstTransition(commonPrefix.get(currentIndex - 1), sentence[currentIndex - 1]);
			transition.setTarget(lastState);
			// TODO: These two lines are a trick for right hash
			register.remove(commonPrefix.get(currentIndex - 1));
			register.put(commonPrefix.get(currentIndex - 1), commonPrefix.get(currentIndex - 1).getId());
			register.put(lastState, lastState.getId());
		}
		else {
			currentIndex = commonPrefix.size() - 1;
		}

		// Check if there are changes of right languages recursively to the
		// initial state.
		boolean changed = true;
		while (changed & currentIndex > 0) {
			currentIndex--;
			currentState = commonPrefix.get(currentIndex);
			State<T> oldState = lastState;
			register.remove(lastState);
			replaceOrRegister(currentState, sentence[currentIndex]);
			changed = oldState != lastState;
		}
	}

	public void orederedAdd(T[] sentence) {

	}
}
